package org.example.myleet.rosalind.lia;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;

public class Solution {

    //经过推导，结果表明，题目给出的每个个体不断地和AaBb个体交配产生后代，则后代中AaBb的概率是四分之一也就是0.25
    //因此非AaBb的概率是四分之三也就是0.75
    private static final BigDecimal AaBb_PROBABILITY = new BigDecimal("0.25");
    private static final BigDecimal NON_AaBb_PROBABILITY = new BigDecimal("0.75");

    public String atLeastNAaBbProbability(Integer k, Integer N) {
        int totalOffspring = (int) Math.pow(2, k);
        BigDecimal totalProbability = BigDecimal.ZERO;
        for (int i = N; i <= totalOffspring; ++i) {
            //每个循环计算有i个AaBb的概率是多少，对从i=N开始到i=totalOffspring的所有情况的概率进行累加就是答案
            //实际计算中由于小数很小，组合数很大，因此需要使用大数字运算
            BigDecimal probability = BigDecimal.ONE;
            for (int j = 0; j < i; ++j) {
                //总共有i个AaBb的概率
                probability = probability.multiply(AaBb_PROBABILITY);
            }
            for (int j = 0; j < (totalOffspring - i); ++j) {
                //总共有(totalOffspring - i)个非AaBb的概率
                probability = probability.multiply(NON_AaBb_PROBABILITY);
            }
            //取i个AaBb且有(totalOffspring - i)个非AaBb的组合数
            BigDecimal combineCount = combination(totalOffspring, i);
            //单个概率*组合数就是这种情况的总概率
            probability = probability.multiply(combineCount);
            //算出一种情况的概率，累加
            totalProbability = totalProbability.add(probability);
        }
        return totalProbability.setScale(10, RoundingMode.HALF_UP).toPlainString();
    }

    private BigDecimal combination(int total, int choose) {
        return factorial(total).divide(factorial(choose).multiply(factorial(total - choose)));
    }

    private BigDecimal factorial(int n) {
        BigDecimal f = BigDecimal.ONE;
        for (int i = 2; i <= n; ++i) {
            f = f.multiply(BigDecimal.valueOf(i));
        }
        return f;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.atLeastNAaBbProbability(2, 1));
        System.out.println(solution.atLeastNAaBbProbability(5, 9));
        System.out.println(solution.atLeastNAaBbProbability(6, 18));
        System.out.println(solution.atLeastNAaBbProbability(6, 15));
    }
}
